/**
 * [95] 不同的二叉搜索树 II
 *
 * @format
 * @lc app=leetcode.cn id=95 lang=javascript
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
// 递归 + 哈希
var generateTrees = function (n) {
    const nums = []
    for (let i = 0; i < n; i++) nums.push(i + 1)
    function generation(nums) {
        if (nums.length == 0) return [null]
        if (nums.length == 1) return [TreeNode(nums[0])]
        if (nums.length == 2) return [TreeNode(nums[0], null, nums[1]), TreeNode(nums[1], nums[0], null)]
        const results = []
        for (let i = 0; i < nums.length; i++) {
            const lefts = generation(nums.slice(0, i))
            const rights = generation(nums.slice(i + 1))
            results.push(...lefts.map(nodeL => rights.map(nodeR => TreeNode(nums[i], nodeL, nodeR))))
        }
        return results
    }
    return generation(nums)
}
debugger
const results = generateTrees(3)
results.forEach(tree => console.log(tree))
// @lc code=end
